package leetcode.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author wangmaolin1
 * @date 2022/1/5 下午9:36
 */
public class _572另一颗树的子树 {

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.val == subRoot.val) {
                if (isSame(node, subRoot)) {
                    return true;
                }
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return false;
    }

    private boolean isSame(TreeNode node, TreeNode subRoot) {
        if (node == null && subRoot == null) {
            return true;
        }
        if (node == null || subRoot == null) {
            return false;
        }
        boolean isSameLeft = isSame(node.left, subRoot.left);
        boolean isSameRight = isSame(node.right, subRoot.right);
        return isSameLeft && isSameRight && node.val == subRoot.val;
    }

    /*
            3
         4    5
      1    2

               4
             1    2
          1
     */
    public static void main(String[] args) {

    }

}
